package leetcode_day._2021._202104._2131;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/4/21 8:42
 * 解码方法
 * 动态规划
 * 计算前 i 个能够组成的最大个数
 * A --> 1  z --> 26
 * 字符串不能以 0 开头，因为所有数组都要映射
 * 因为最大只有两位数，且不能超过 26，所以可以考虑两种情况
 * 1、当只使用 s.charAt(i) 进行解码时 , dp[i] += dp[i - 1] s.charAt(i) != '0'
 * 2、当使用 s.charAt(i) 和 s.charAt(i - 1) 进行解码时，dp[i] += dp[i - 2]
 *   s.charAt(i) != '0' && s.charAt(i - 1)s.chartAt(i - 2) <= 26
 * dp 的长度为 s.length() + 1 , 规定 dp[0] = 1 , 这样可以避免判断 i - 1
 */
public class _21_91 {
    public static void main(String[] args) {
        System.out.println(new _21_91().numDecodings_perfect("2101"));
    }

    public int numDecodings(String s) {
        if (s.length() == 0 || s.charAt(0) == '0') return 0;
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for (int i = 1; i <= s.length(); i++) {
            if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1];
            if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0') <= 26)
                dp[i] += dp[i - 2];
        }
        return dp[s.length()];
    }


    public int numDecodings_perfect(String s) {
        if (s.length() == 0 || s.charAt(0) == '0') return 0;
        int pre = 0, cur = 1;
        for (int i = 1; i <= s.length(); i++) {
            System.out.println(i + " --> pre : " + pre + ", cur : " + cur);
            int tmp = 0;
            if (s.charAt(i - 1) != '0') tmp += cur;
            if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0') <= 26)
                tmp += pre;
            pre = cur;
            cur = tmp;
        }
        return cur;
    }
}





